package com.ls.day15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author ：xxx
 * @description：TODO
 * @date ：2021/3/31 22:21
 */
public class CombinationSum2 {
    public List<List<Integer>> res = new ArrayList<List<Integer>>();
    public List<Integer> temp = new ArrayList<Integer>();
    boolean[] visit = new boolean[100];
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        getres(candidates,target);
        return res;
    }

    void getres(int[] candidates, int target){
        if (target==0){
            List<Integer> a = new ArrayList<>(temp);
            res.add(a);
            return;
        }
        int i=0,p=0;
        for (i=0;i<candidates.length;i++){
            if (!visit[i] && candidates[i]<=target){
                if (temp.size()>0 && candidates[i]<temp.get(temp.size()-1)) continue;       //去除逆序
                visit[i]=true;
                temp.add(candidates[i]);
                getres(candidates,target-candidates[i]);
                visit[i]=false;
                temp.remove(temp.size()-1);
                p=i;
                while (i<candidates.length && candidates[p]==candidates[i])i++; //去重  相同的情况如 1 1，则前面的1遍历时包括了后面的1的情况
                i--;
            }
        }
    }

}
